#pragma once
#include <iostream>
#include <vector>
#include <string>

namespace cr
{
    template <class T>
    struct BSTNode
    {
        BSTNode(const T &val = T())
            : _val(val), _left(nullptr), _right(nullptr) {}

        T _val;
        BSTNode *_left;
        BSTNode *_right;
    };

    template <class T>
    class BSTree
    {
        typedef BSTNode<T> Node;

        void copy(Node *&root, Node *tmp)
        {
            if (tmp == nullptr)
                return;
            root = new Node(tmp->_val);
            copy(root->_left, tmp->_left);
            copy(root->_right, tmp->_right);
        }

    public:
        BSTree()
            : _proot(nullptr) {}
        BSTree(const BSTree &tmp)
        {
            copy(_proot, tmp._proot);
        }
        const BSTree &operator=(BSTree tmp)
        {
            std::swap(_proot, tmp._proot);
            return *this;
        }

        bool insert(const T &val)
        {
            Node *newnode = new Node(val);
            if (_proot == nullptr)
            {
                _proot = newnode;
                return true;
            }
            Node *cur = _proot;
            while (cur)
            {
                if (val > cur->_val)
                {
                    if (cur->_right == nullptr)
                    {
                        cur->_right = newnode;
                        break;
                    }
                    cur = cur->_right;
                }
                else if (val < cur->_val)
                {
                    if (cur->_left == nullptr)
                    {
                        cur->_left = newnode;
                        break;
                    }
                    cur = cur->_left;
                }
                else
                    return false;
            }
            return true;
        }
        bool erase(const T &val)
        {
            // 1.如果该节点是单树-》直接删除
            // 2.如果该节点有左右孩子-》左边找最大节点||右边找最小节点

            // 找待删除节点cur和其父节点parent
            Node *cur = _proot, *parent = nullptr;
            while (cur)
            {
                if (val > cur->_val)
                {
                    parent = cur;
                    cur = cur->_right;
                }
                else if (val < cur->_val)
                {
                    parent = cur;
                    cur = cur->_left;
                }
                else
                {
                    break;
                }
            }
            if (cur == nullptr) // 没找到
                return false;
            if (cur->_left && cur->_right)
            {
                // 找右边最小值节点tmp,和其父节点ptmp
                Node *tmp = cur->_right, *ptmp = cur; // tmp不为空
                while (tmp->_left)
                {
                    ptmp = tmp;
                    tmp = tmp->_left;
                }

                // 右边最小值节点就是第一个右节点
                if (ptmp == cur) // 最左节点是父节点的右
                {
                    cur->_val = tmp->_val;
                    ptmp->_right = tmp->_right;
                }
                else // 最左节点是父节点的左
                {
                    cur->_val = tmp->_val;
                    ptmp->_left = tmp->_right; // 可能最小值节点tmp有右节点
                }

                delete tmp;
            }
            else if (cur->_left == nullptr) // 全为空也会进来
            {
                if (cur == _proot)
                {
                    _proot = cur->_right;
                }
                else
                {
                    if (parent->_left == cur)
                    {
                        parent->_left = cur->_right;
                    }
                    else
                    {
                        parent->_right = cur->_right;
                    }
                }

                delete cur;
            }
            else if (cur->_right == nullptr)
            {
                if (cur == _proot)
                {
                    _proot = cur->_left;
                }
                else
                {
                    if (parent->_left == cur)
                    {
                        parent->_left = cur->_left;
                    }
                    else
                    {
                        parent->_right = cur->_left;
                    }
                }
                delete cur;
            }
            return true;
        }
        bool find(const T &val)
        {
            Node *cur = _proot;
            while (cur)
            {
                if (val > cur->_val)
                {
                    cur = cur->_right;
                }
                else if (val < cur->_val)
                {
                    cur = cur->left;
                }
                else
                {
                    return true;
                }
            }
            return false;
        }
        void inorder()
        {
            midOrder(_proot);
            std::cout << std::endl;
        }
        ~BSTree()
        {
            Destroy(_proot);
        }

    private:
        void midOrder(Node *cur)
        {
            if (cur == nullptr)
                return;
            midOrder(cur->_left);
            std::cout << cur->_val << ' ';
            midOrder(cur->_right);
        }
        void Destroy(Node *cur)
        {
            if (cur == nullptr)
                return;
            Destroy(cur->_left);
            Destroy(cur->_right);
            delete cur;
            cur = nullptr;
        }

    private:
        Node *_proot;
    };
}